Параллельный алгоритм

В информатике параллельный алгоритм, противопоставляемый традиционным последовательным алгоритмам, — алгоритм, который может быть реализован по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов и получением корректного результата.

Некоторые алгоритмы достаточно просто поддаются разбиению на независимо выполняемые фрагменты. Например, распределение работы по проверке всех чисел от 1 до 100000 на предмет того, какие из них являются простыми, может быть выполнено путём назначения каждому доступному процессору некоторого подмножества чисел с последующим объединением полученных множеств простых чисел (похожим образом реализован, например, проект GIMPS).

С другой стороны, большинство известных алгоритмов вычисления значения числа пи ($\pi$) не допускают разбиения на параллельно выполняемые части, так как требуют результата предыдущей итерации выполнения алгоритма. Итеративные численные методы, такие как, например, метод Ньютона или задача трёх тел, также являются сугубо последовательными алгоритмами. Некоторые примеры рекурсивных алгоритмов достаточно сложно поддаются распараллеливанию. Одним из примеров является поиск в глубину на графах.

Параллельные алгоритмы весьма важны ввиду постоянного совершенствования многопроцессорных систем и увеличения числа ядер в современных процессорах. Обычно проще сконструировать компьютер с одним быстрым процессором, чем с множеством медленных процессоров (при условии достижения одинаковой производительности). Однако производительность процессоров увеличивается главным образом за счёт совершенствования техпроцесса (уменьшения норм производства), чему мешают физические ограничения на размер элементов микросхем и тепловыделение. Указанные ограничения могут быть преодолены путём перехода к многопроцессорной обработке, что оказывается эффективным даже для малых вычислительных систем.

Сложность последовательных алгоритмов выражается в объёме используемой памяти и времени (числе тактов процессора), необходимых для выполнения алгоритма. Параллельные алгоритмы требуют учёта использования ещё одного ресурса: подсистемы связей между различными процессорами. Существует два способа обмена между процессорами: использование общей памяти и системы передачи сообщений.

Системы с общей памятью требуют введения дополнительных блокировок для обрабатываемых данных, налагая определённые ограничения при использовании дополнительных процессоров.

Системы передачи сообщений используют понятия каналов и блоков сообщений, что создаёт дополнительный трафик на шине и требует дополнительных затрат памяти для организации очередей сообщений. В дизайне современных процессоров могут быть предусмотрены специальные коммутаторы (кроссбары) с целью уменьшения влияния обмена сообщениями на время выполнения задачи.

Ещё одной проблемой, связанной с использованием параллельных алгоритмов, является балансировка нагрузки. Например, поиск простых чисел в диапазоне от 1 до 100000 легко распределить между имеющимися процессорами, однако некоторые процессоры могут получить больший объём работы, в то время как другие закончат обработку раньше и будут простаивать. Проблемы балансировки нагрузки ещё больше усугубляется при использовании гетерогенных вычислительных сред, в которых вычислительные элементы существенно отличаются по производительности и доступности (например, в грид-системах).

Разновидность параллельных алгоритмов, называемая распределёнными алгоритмами, специально разрабатываются для применения на кластерах и в распределённых вычислительных системах с учётом ряда особенностей подобной обработки.

См. также

• Искусственная нейронная сеть
• Параллельные вычислительные системы

Ссылки

• Designing and Building Parallel Programs page at the US Argonne National Laboratories

web-архивы

• Parallel Algorithm Design